class Solution {
    public:
        int is_existent[20][20] = {0};
        int targeti,targetj;
        int spacesum = 0;
        int path=0;
        int ret = 0;
        int uniquePathsIII(vector<vector<int>>& grid) {
            int n = grid.size(),m=grid[0].size();
            int starti,startj;
            for(int i = 0 ; i < n ; i++ ){
                for(int j = 0 ; j < m ; j++){
                    if(grid[i][j] == 1){
                        starti = i;startj = j;
                    }else if( grid[i][j] == 2){
                        targeti = i;targetj = j;
                    }else if( grid[i][j] == 0){
                        spacesum++;
                    }
                }
            }
            is_existent[starti][startj] = 1; //用未被注释的方法一定要记得将初始点设置为已走过！！！！！！！！
            dfs(grid,starti,startj);
            return ret;
        }
        int indexx[4]={-1,1,0,0};
        int indexy[4]={0,0,-1,1};
        void dfs(vector<vector<int>> grid,int i , int j){
            // cout<<i<<" "<<j<<" "<<targeti<<" "<<targetj<<" "<<path<<" "<<spacesum<< endl;
            if(i == targeti && j ==targetj){
                if(path == spacesum)    ret++;
                return;
            }
            int n = grid.size(),m=grid[0].size();
            // if(i >=0 && i < n&& j >=0 && j<m && grid[i][j] != -1 && is_existent[i][j] ==0){
            //     if(grid[i][j] == 0) path++;
            //     is_existent[i][j] = 1;
            //     //向上下左右
            //     dfs(grid,i-1,j);
            //     dfs(grid,i+1,j);
            //     dfs(grid,i,j-1);
            //     dfs(grid,i,j+1);
            //     if(grid[i][j] == 0) path--;
            //     is_existent[i][j] = 0;
            // }
            for(int k = 0; k < 4 ; k++){
                int row = i+indexx[k];
                int col = j + indexy[k];
                if(row >=0 && row < n && col>=0&&col < m && grid[row][col] !=-1 && is_existent[row][col] == 0){
                    if(grid[row][col] == 0) path++;
                    is_existent[row][col] = 1;
                    dfs(grid,row,col);
                    if(grid[row][col] == 0) path--;
                    is_existent[row][col] = 0;
                }
            }
        }
    };